package com.zlk.algorithm.dataStructure.graph.topological;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;

/**
 * @program: algorithm
 * @ClassName TopologicalOrderDFS1
 * @description:https://www.lintcode.com/problem/topological-sorting
 * 利用深度来处理拓扑排序
 * 深度长的肯定排前面
 * @author: slfang
 * @create: 2024-03-20 14:59
 * @Version 1.0
 **/
public class TopologicalOrderDFS1 {

    public static class DirectedGraphNode {
        public int label;
        public ArrayList<DirectedGraphNode> neighbors;

        public DirectedGraphNode(int x) {
            label = x;
            neighbors = new ArrayList<DirectedGraphNode>();
        }
    }

    class Record{
        DirectedGraphNode node;
        int deep;

        public Record(DirectedGraphNode node, int deep) {
            this.node = node;
            this.deep = deep;
        }
    }
    public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        HashMap<DirectedGraphNode,Record> order = new HashMap<>();
        for (DirectedGraphNode directedGraphNode : graph) {
            f(directedGraphNode,order);
        }
        ArrayList<Record> records = new ArrayList<>();
        Collection<Record> values = order.values();
        for (Record value : values) {
            records.add(value);
        }
        records.sort((a,b)->b.deep-a.deep);
        ArrayList<DirectedGraphNode> ans = new ArrayList<DirectedGraphNode>();
        for (Record r : records) {
            ans.add(r.node);
        }
        return ans;
    }

    private Record f(DirectedGraphNode directedGraphNode, HashMap<DirectedGraphNode,Record> order) {
        //如果不加判断会导致records重复加入,使用map也会避免重复查询
        if(order.containsKey(directedGraphNode)){
            return order.get(directedGraphNode);
        }
        int initDeep = 0;
        for (DirectedGraphNode neighbor : directedGraphNode.neighbors) {
            initDeep = Math.max(initDeep,f(neighbor,order).deep);
        }
        // 不+1，所有节点深度都是0
        Record record = new Record(directedGraphNode, initDeep+1);
        order.put(directedGraphNode,record);
        return record;
    }

}
